package com.sakura.动态规划;

public class Code516_最长回文子序列 {

    public int longestPalindromeSubseq1(String str) {
        return f1(str.toCharArray(), 0, str.length() - 1);
    }

    private int f1(char[] s, int L, int R) {
        if (L == R) {
            return 1;
        }
        if (L > R) {
            return 0;
        }
        if (s[L] == s[R]) {
            return f1(s, L + 1, R - 1) + 2;
        } else {
            return Math.max(f1(s, L + 1, R), f1(s, L, R - 1));
        }
    }

    public int longestPalindromeSubseq2(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        int[][] dp = new int[n][n];
        return f2(s, 0, n - 1, dp);
    }

    private int f2(char[] s, int L, int R, int[][] dp) {
        if (L == R) {
            return 1;
        }
        if (L > R) {
            return 0;
        }
        if (dp[L][R] != 0) {
            return dp[L][R];
        }
        int ans;
        if (s[L] == s[R]) {
            ans = f2(s, L + 1, R - 1, dp) + 2;
        } else {
            ans = Math.max(f2(s, L + 1, R, dp), f2(s, L, R - 1, dp));
        }
        dp[L][R] = ans;
        return ans;
    }

    public int longestPalindromeSubseq3(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        int[][] dp = new int[n][n];
        for (int l = n - 1; l >= 0; l--) {
            dp[l][l] = 1; // L <= R,对角线为1
            if (l + 1 < n) {
                dp[l][l + 1] = s[l] == s[l + 1] ? 2 : 1;
            }
            for (int r = l + 2; r < n; r++) {
                if (s[l] == s[r]) {
                    dp[l][r] = dp[l + 1][r - 1] + 2;
                } else {
                    dp[l][r] = Math.max(dp[l + 1][r], dp[l][r - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
}
